package com.qz.sort;

/**
 * @Description 希尔排序，从小到大
 * @Author Flag
 * @Date: 2021/8/1 11:04
 * @Version: 1.0
 **/
public class ShellSortDome {
    public static void main(String[] args) {
        int [] array = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("初始数组");
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");

        }
        System.out.println("开始排序");
        System.out.println();
        int[] ints = shellSort55(array);
        System.out.println("结束排序");
        for (int i = 0; i < ints.length; i++) {
            System.out.print(array[i]+" ");

        }
    }

    /**
     * 希尔排序
     * 首先取步长
     *
     * @param array
     * @return
     */
    public static int[] shellSort(int[] array,int lastStepLenght){
        //第一组 int [] array = {8,9,1,7,2,3,5,4,0};
        int stepLenght = array.length/2;

        //外层控制步长
        int j = 0;
        for (int i = 0; i < stepLenght; i++) {
            //内层控制遍历的每一次
            for (; j < (i+1)*stepLenght; j++) {
                //排序
            }
        }


        return shellSort(array, stepLenght);

    }


    /**
     * 希尔排序 ，从小到大
     * @param array
     * @param lastStepLenght
     * @return
     */
    public static int[] shellSort2(int[] array){

        int h=4;
        //求出累加度
//        while (h > array.length /2){
//            //计数累加
//            h = 2*h+1;
//        }

        int temp=0;
        //第一轮
        //while循环来管理每次缩小的部分
        while (h>0){
            //这两层循环，组成了插入排序，只不过，这里是间隔h进行计算
            for (int i = h; i <array.length; i++) {
                //获取到每一个拆入的位置
                int insertValue = array[i];
                //获取到比较的前一个元素
                int insertIndex = i-h;
                //要么超出了索引的界限，要么找到了合适的位置
                while (insertIndex>= 0 && array[insertIndex] > insertValue){
                    //否则，数据就一直移动
                    array[insertIndex+h] = array[insertIndex];
                    //索引减小
                    insertIndex -=h ;
                }
                //将提前预制的数据放到获得的位置
                array[insertIndex+h] = insertValue;


                //遍历当前节点前面的每一个元素
//                for (int j = i;j>=h;j-=h) {
//                    //如果发现，比自己小，就结束
//                    if(array[j] < array[j-h]){
//                        temp = array[j];
//                        array[j] = array[j-h];
//                        array[j-h] = temp;
//                    } else {
//                        break;
//                    }
//                }
            }
            h /=2;
        }


        return array;
    }


    /**
     * 希尔排序
     * 什么是希尔排序?
     * 希尔排序是先分组,把一组数据分成多干组,然后每组有步长,再进行插入排序
     *
     *
     *
     * @param array
     * @return
     */
    public static int[] shellSort3(int[] array){

        int h = array.length/2;
        while (h< array.length/2){
            h = 2*h + 1;
        }


        int insertIndex;
        int insertValue;
        //该次循环,用于控制每次改变步长后的循环
        while (h>0){

            for (int i = h; i < array.length; i++) {
                insertValue = array[i];
                insertIndex = i - h;
                while (insertIndex>=0 && array[insertIndex] > insertValue){
                    array[insertIndex+h] = array[insertIndex];
                    insertIndex -=h;
                }
                array[insertIndex+h] = insertValue;


            }




            h /=2;
        }

        return array;
    }


    /**
     * 希尔排序， 从小到大
     * @param array
     * @return
     */
    public static int[] shellSort4(int[] array){
//        int [] array = {8,9,1,7,2,3,5,4,0};
        //第一组
        //1.求出步长
        int h = array.length /2 ;

        //通过插入排序方式进行排序，只不过步长从1变成h
        while (h >= 1){
            for (int j = h; j < array.length; j++) {
                int index = j-h;
                int insertValue = array[j];
                while ( index >=0 && array[index] > insertValue){
                    //将前一个数据覆盖掉后一个数据
                    array[index+h] = array[index];
                    index-=h;
                }
                array[index + h ] = insertValue;
            }


            h /=2;
        }


        //4.返回结果


        return array;

    }

    //        int [] array = {8,9,1,7,2,3,5,4,0};

    /**
     * 希尔排序 从小到大
     *
     * 其实就是牛逼版本的拆入排序
     *
     *
     * @param array
     * @return
     */
    public static int[] shellSort55(int[] array){
        //第一轮
        //求出步长
        int h = 4;

        int insertValue;
        int insertIndex;
        while (h >= 1){
            for (int i = h; i < array.length ; i++) {

                insertValue = array[i];
                insertIndex = i - h;

                while (insertIndex >=0 && array[insertIndex] > insertValue){
                    array[insertIndex + h ] = array[insertIndex];
                    insertIndex -= h ;
                }

                array[insertIndex+h] = insertValue;


            }
            h /= 2;
        }

        return array;







    }

 }
